package simple.array;

import java.util.ArrayDeque;

/**
 * <a href="https://leetcode.cn/problems/duplicate-zeros/">1089. 复写零</a>
 * 给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
 * 注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
 * 示例 1：
 *   输入：arr = [1,0,2,3,0,4,5,0]
 *   输出：[1,0,0,2,3,0,0,4]
 *   解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
 * 示例 2：
 *   输入：arr = [1,2,3]
 *   输出：[1,2,3]
 *   解释：调用函数后，输入的数组将被修改为：[1,2,3]
 * 提示：
 *   1 <= arr.length <= 10^4
 *   0 <= arr[i] <= 9
 * @author 刘学松
 * @date 2023-07-11 8:42
 */
public class 复写零 {
    public static void main(String[] args) {
        duplicateZeros1(new int[]{1,5,2,0,6,8,0,6,0});
    }
    public static void duplicateZeros(int[] arr) {
        int zeroCount = 0;
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < arr.length; i++) {
            queue.add(arr[i]);
            if (zeroCount == 0) {
                int out = queue.removeFirst();
                if (out == 0) {
                    ++zeroCount;
                }
                arr[i] = out;
            } else {
                arr[i] = 0;
                --zeroCount;
            }
        }
    }

    /**
     * 双指针
     * @param arr
     */
    public static void duplicateZeros1(int[] arr) {
        int length = arr.length;
        int left = -1,right = 0;
        // 先确定指针边界，以右指针为止
        while (right < length) {
            ++left;
            if (arr[left] == 0) {
                right += 2;
            } else {
                ++right;
            }
        }
        // 出现了length+1的情况，一定是最后遇到0了，因此将数组最后一个位置置为0，为了防止越界，将右指针-1或-2
        if (right == length + 1) {
            arr[length - 1] = 0;
            --left;
            right = length - 2;
        } else {
            right = length - 1;
        }

        while (right > 0) {
            arr[right] = arr[left];
            --right;
            if (arr[left] == 0) {
                arr[right] = 0;
                --right;
            }
            --left;
        }
    }
}
